package main.java.indi.zyj.c150.dps;

import java.util.Scanner;

/**

         S....
         .###.
         .###.
         .###.
         ....e

 */
public class _03_MazeTotalSolution {


    static int m, n, ans;
    static boolean[][] visited = new boolean[11][11];
    static Character[][] maze = new Character[11][11];
    static int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

    public static boolean In(int x, int y){
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    public static void Dfs(int x, int y){

        if (!In(x, y) || maze[x][y] == '#' || visited[x][y]){
            return;
        }

        if (maze[x][y] == 'e'){
            ans++;
            return;
        }

        visited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i][0], nextY = y + dir[i][1];
            Dfs(nextX, nextY);
        }

        visited[x][y] = false;

    }

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int x = 0;
        int y = 0;

        System.out.println("请输入迷宫的行列数:");
        m = scan.nextInt();
        n = scan.nextInt();

        for (int i = 0; i <m ; i++) {
            String s=scan.next();
            for (int j = 0; j <n ; j++) {
                maze[i][j] = s.charAt(j);
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (maze[i][j] == 'S'){
                    x = i;
                    y = j;
                }
            }
        }

        Dfs(x, y);
        System.out.println("总共可以到达终点的路径数为：" + ans);

    }

}
